package tree

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/*
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/
*/
/*
时间复杂度:O(n)
空间复杂度:O(1)
 */
func flatten(root *TreeNode) {
	cur := root
	// 将左子树界点均转换为右子树节点
	for cur != nil {
		if cur.Left != nil {
			next := cur.Left
			tail := next
			// 寻找左子树的最后一个节点
			for tail.Right != nil {
				tail = tail.Right
			}
			tail.Right = cur.Right
			cur.Left, cur.Right = nil, next
		}
		cur = cur.Right
	}
}
